<!DOCTYPE html>












  


<html class="theme-next muse use-motion" lang="zh-CN">
<head><meta name="generator" content="Hexo 3.8.0">
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">












<meta http-equiv="Cache-Control" content="no-transform">
<meta http-equiv="Cache-Control" content="no-siteapp">






















<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css">

<link href="/css/main.css?v=6.3.0" rel="stylesheet" type="text/css">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=6.3.0">


  <link rel="icon" type="image/png" sizes="32x32" href="/favicon.ico?v=6.3.0">


  <link rel="icon" type="image/png" sizes="16x16" href="/favicon.ico?v=6.3.0">


  <link rel="mask-icon" href="/images/logo.svg?v=6.3.0" color="#222">









<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Muse',
    version: '6.3.0',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: false,
    fastclick: false,
    lazyload: false,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>


  




  <meta name="description" content="LeetCode 1. Two Sum (两数之和) Diffculty: Eazy">
<meta name="keywords" content="LeetCode,Algorithms">
<meta property="og:type" content="article">
<meta property="og:title" content="[LeetCode] 1. Two Sum">
<meta property="og:url" content="https://yamdestiny.xyz/2019/04/01/leetcode-1-two-sum/index.html">
<meta property="og:site_name" content="Yamdestiny">
<meta property="og:description" content="LeetCode 1. Two Sum (两数之和) Diffculty: Eazy">
<meta property="og:locale" content="zh-CN">
<meta property="og:updated_time" content="2019-04-09T01:22:27.602Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="[LeetCode] 1. Two Sum">
<meta name="twitter:description" content="LeetCode 1. Two Sum (两数之和) Diffculty: Eazy">






  <link rel="canonical" href="https://yamdestiny.xyz/2019/04/01/leetcode-1-two-sum/">



<script type="text/javascript" id="page.configurations">
  CONFIG.page = {
    sidebar: "",
  };
</script>

  <title>[LeetCode] 1. Two Sum | Yamdestiny</title>
  




<script async src="https://www.googletagmanager.com/gtag/js?id=UA-92396016-1"></script>
<script>
  window.dataLayer = window.dataLayer || [];
  function gtag(){dataLayer.push(arguments);}
  gtag('js', new Date());

  gtag('config', 'UA-92396016-1');
</script>



  <script type="text/javascript">
    var _hmt = _hmt || [];
    (function() {
      var hm = document.createElement("script");
      hm.src = "https://hm.baidu.com/hm.js?4eacbd1e85d8eebe356b663a83063d78";
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(hm, s);
    })();
  </script>




  <noscript>
  <style type="text/css">
    .use-motion .motion-element,
    .use-motion .brand,
    .use-motion .menu-item,
    .sidebar-inner,
    .use-motion .post-block,
    .use-motion .pagination,
    .use-motion .comments,
    .use-motion .post-header,
    .use-motion .post-body,
    .use-motion .collection-title { opacity: initial; }

    .use-motion .logo,
    .use-motion .site-title,
    .use-motion .site-subtitle {
      opacity: initial;
      top: initial;
    }

    .use-motion {
      .logo-line-before i { left: initial; }
      .logo-line-after i { right: initial; }
    }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-CN">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">Yamdestiny</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
    
  </div>

  <div class="site-nav-toggle">
    <button aria-label="切换导航栏">
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>



<nav class="site-nav">
  
    <ul id="menu" class="menu">
      
        
        
        
          
          <li class="menu-item menu-item-home">
    <a href="/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-home"></i> <br>首页</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-tags">
    <a href="/tags/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-tags"></i> <br>标签</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-categories">
    <a href="/categories/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-th"></i> <br>分类</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-archives">
    <a href="/archives/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-archive"></i> <br>归档</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-series">
    <a href="/series/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-sitemap"></i> <br>系列</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-resource">
    <a href="/resource/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-file"></i> <br>资源</a>
  </li>

      
      
    </ul>
  

  
    

  

  
</nav>



  



</div>
    </header>

    
  
  
  
    
      
    
    <a href="https://github.com/YamDestiny" class="github-corner" target="_blank" title="Follow me on GitHub" aria-label="Follow me on GitHub"><svg width="80" height="80" viewbox="0 0 250 250" style="fill:#222; color:#fff; position: absolute; top: 0; border: 0; right: 0;" aria-hidden="true"><path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"/><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"/><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"/></svg>
    
      </a>
    



    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://yamdestiny.xyz/2019/04/01/leetcode-1-two-sum/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="YamDestiny">
      <meta itemprop="description" content="以铜为镜，可以正衣冠；<br />以史为镜，可以知兴替；<br />以人为镜，可以明得失。">
      <meta itemprop="image" content="https://p3.music.126.net/Am30CzvY9NTxy1xiz5k3GQ==/7729566744520405.jpg?param=170y170">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Yamdestiny">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">[LeetCode] 1. Two Sum
              
            
          </h1>
        

        <div class="post-meta">
          <span class="post-time">

            
            
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              

              
                
              

              <time title="创建时间：2019-04-01 21:26:40" itemprop="dateCreated datePublished" datetime="2019-04-01T21:26:40+08:00">2019-04-01</time>
            

            
              

              
                
                <span class="post-meta-divider">|</span>
                

                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                
                  <span class="post-meta-item-text">更新于</span>
                
                <time title="修改时间：2019-04-09 09:22:27" itemprop="dateModified" datetime="2019-04-09T09:22:27+08:00">2019-04-09</time>
              
            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing"><a href="/categories/衣带渐宽终不悔，为伊消得人憔悴/" itemprop="url" rel="index"><span itemprop="name">衣带渐宽终不悔，为伊消得人憔悴</span></a></span>

                
                
                  ，
                
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing"><a href="/categories/衣带渐宽终不悔，为伊消得人憔悴/LeetCode/" itemprop="url" rel="index"><span itemprop="name">LeetCode</span></a></span>

                
                
                  ，
                
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing"><a href="/categories/衣带渐宽终不悔，为伊消得人憔悴/LeetCode/Algorithms/" itemprop="url" rel="index"><span itemprop="name">Algorithms</span></a></span>

                
                
              
            </span>
          

          
            
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
                <a href="/2019/04/01/leetcode-1-two-sum/#comments" itemprop="discussionUrl">
                
                  <span class="post-comments-count disqus-comment-count" data-disqus-identifier="2019/04/01/leetcode-1-two-sum/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          
             <span id="/2019/04/01/leetcode-1-two-sum/" class="leancloud_visitors" data-flag-title="[LeetCode] 1. Two Sum">
               <span class="post-meta-divider">|</span>
               <span class="post-meta-item-icon">
                 <i class="fa fa-eye"></i>
               </span>
               
                 <span class="post-meta-item-text">阅读次数：</span>
               
                 <span class="leancloud-visitors-count"></span>
             </span>
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <p>LeetCode 1. Two Sum (两数之和) Diffculty: Eazy</p>
<a id="more"></a>
<h2 id="Question"><a href="#Question" class="headerlink" title="Question"></a>Question</h2><p>Given an array of integers, return indices of the two numbers such that they add up to a specific target.</p>
<p>You may assume that each input would have exactly one solution, and you may not use the same element twice.</p>
<p>给定一个整数数组 <code>nums</code> 和一个目标值 <code>target</code>，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。</p>
<p>你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。</p>
<h2 id="Example"><a href="#Example" class="headerlink" title="Example"></a>Example</h2><h3 id="Example-1"><a href="#Example-1" class="headerlink" title="Example 1"></a>Example 1</h3><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">Given nums = [2, 7, 11, 15], target = 9,</span><br><span class="line"></span><br><span class="line">Because nums[0] + nums[1] = 2 + 7 = 9,</span><br><span class="line">return [0, 1].</span><br></pre></td></tr></table></figure>
<h3 id="Example-2"><a href="#Example-2" class="headerlink" title="Example 2"></a>Example 2</h3><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">[3, 2, 3]</span><br><span class="line">6</span><br></pre></td></tr></table></figure>
<h2 id="Solution"><a href="#Solution" class="headerlink" title="Solution"></a>Solution</h2><p>题意分析</p>
<ul>
<li>Input：一个整数数组 <code>nums</code>；一个目标值 <code>target</code></li>
<li>Output： 数组中两个元素之和等于目标值的两个元素的下标组成的一个长度为 <code>2</code> 的整数数组</li>
<li>即是需要从 nums 中依次遍历，计算并判断 <code>n</code> 和 <code>n + 1</code> 的和（<code>nums[n] + nums[n + 1] == target</code>），然后将 <code>n</code> 和 <code>n + 1</code> 作为数组输出结果（<code>[n, n + 1]</code>）</li>
<li><code>n</code> 的范围是 <code>[0, nums.length)</code></li>
</ul>
<h3 id="Java"><a href="#Java" class="headerlink" title="Java"></a>Java</h3><h4 id="My-Solution-1"><a href="#My-Solution-1" class="headerlink" title="My Solution 1"></a>My Solution 1</h4><h5 id="解题思路"><a href="#解题思路" class="headerlink" title="解题思路"></a>解题思路</h5><p>用两个循环分别遍历数组索引为 <code>n</code> 和 <code>n + 1</code> 的元素，并判断两个元素之和是否与目标值相同。</p>
<h5 id="解题步骤"><a href="#解题步骤" class="headerlink" title="解题步骤"></a>解题步骤</h5><ol>
<li>循环1，范围：<code>[0, nums.length)</code>，获取 <code>n</code> 的元素</li>
<li>循环2，嵌套在循环1中，范围：<code>[1, nums.length)</code>，获取 <code>n + 1</code> 的元素</li>
<li>循环2中，判断 <code>nums[n] + nums[n + 1] == target</code>，如为 <code>true</code>，则 <code>return new int[] {n, n + 1}</code></li>
</ol>
<h5 id="Code"><a href="#Code" class="headerlink" title="Code"></a>Code</h5><h6 id="初版"><a href="#初版" class="headerlink" title="初版"></a>初版</h6><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[] twoSum(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target) &#123;</span><br><span class="line">    <span class="keyword">int</span>[] results = <span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">2</span>];</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span> length = nums.length;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; length; i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = i; j &lt; length; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (j &gt; i) &#123;</span><br><span class="line">                <span class="keyword">int</span> a = nums[i];</span><br><span class="line">                <span class="keyword">int</span> b = nums[j];</span><br><span class="line"></span><br><span class="line">                <span class="keyword">int</span> sum = a + b;</span><br><span class="line">                <span class="keyword">if</span> (sum == target) &#123;</span><br><span class="line">                    results[<span class="number">0</span>] = i;</span><br><span class="line">                    results[<span class="number">1</span>] = j;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> results;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h6 id="优化版"><a href="#优化版" class="headerlink" title="优化版"></a>优化版</h6><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[] twoSum(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target) &#123;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; nums.length; i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = i; j &lt; nums.length; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (j &gt; i &amp;&amp; nums[i] + nums[j] == target) &#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[] &#123; i, j &#125;;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">"No two sum solution"</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h5 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h5><p>这种解题思路实际就与 LeetCode 提供的 Solution 1 一样。</p>
<h4 id="LeetCode-Solution-1-Brute-Force"><a href="#LeetCode-Solution-1-Brute-Force" class="headerlink" title="LeetCode Solution 1: Brute Force"></a>LeetCode Solution 1: Brute Force</h4><p>The brute force approach is simple. Loop through each element xx and find if there is another value that equals to <code>target - x</code>.</p>
<p>暴力法很简单。遍历每个元素 <code>x</code>，并查找是否存在一个值与 <code>target - x</code> 相等的目标元素。</p>
<h5 id="Code-1"><a href="#Code-1" class="headerlink" title="Code"></a>Code</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[] twoSum(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target) &#123;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; nums.length; i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = i + <span class="number">1</span>; j &lt; nums.length; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (nums[j] == target - nums[i]) &#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[] &#123; i, j &#125;;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">"No two sum solution"</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h5 id="Complexity-Analysis"><a href="#Complexity-Analysis" class="headerlink" title="Complexity Analysis"></a>Complexity Analysis</h5><ul>
<li>时间复杂度：$O(n^2)$，对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 $O(n)$ 的时间。因此时间复杂度为 $O(n^2)$。</li>
<li>空间复杂度：$O(1)$。</li>
</ul>
<h4 id="LeetCode-Solution-2-Two-pass-Hash-Table"><a href="#LeetCode-Solution-2-Two-pass-Hash-Table" class="headerlink" title="LeetCode Solution 2: Two-pass Hash Table"></a>LeetCode Solution 2: Two-pass Hash Table</h4><p>To improve our run time complexity, we need a more efficient way to check if the complement exists in the array. If the complement exists, we need to look up its index. What is the best way to maintain a mapping of each element in the array to its index? A hash table.</p>
<p>We reduce the look up time from $O(n)$ to $O(1)$ by trading space for speed. A hash table is built exactly for this purpose, it supports fast look up in near constant time. I say “near” because if a collision occurred, a look up could degenerate to $O(n)$ time. But look up in hash table should be amortized $O(1)$ time as long as the hash function was chosen carefully.</p>
<p>A simple implementation uses two iterations. In the first iteration, we add each element’s value and its index to the table. Then, in the second iteration we check if each element’s complement (<code>target - nums[i]</code>) exists in the table. Beware that the complement must not be <code>nums[i]</code> itself!</p>
<p>为了对运行时间复杂度进行优化，我们需要一种更有效的方法来检查数组中是否存在目标元素。如果存在，我们需要找出它的索引。保持数组中的每个元素与其索引相互对应的最好方法是什么？哈希表。</p>
<p>通过以空间换取速度的方式，我们可以将查找时间从 $O(n)$ 降低到 $O(1)$。哈希表正是为此目的而构建的，它支持以 近似 恒定的时间进行快速查找。我用“近似”来描述，是因为一旦出现冲突，查找用时可能会退化到 $O(n)$。但只要你仔细地挑选哈希函数，在哈希表中进行查找的用时应当被摊销为 $O(1)$。</p>
<p>一个简单的实现使用了两次迭代。在第一次迭代中，我们将每个元素的值和它的索引添加到表中。然后，在第二次迭代中，我们将检查每个元素所对应的目标元素（<code>target - nums[i]</code>）是否存在于表中。注意，该目标元素不能是 <code>nums[i]</code> 本身！</p>
<h5 id="Code-2"><a href="#Code-2" class="headerlink" title="Code"></a>Code</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[] twoSum(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target) &#123;</span><br><span class="line">    Map&lt;Integer, Integer&gt; map = <span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; nums.length; i++) &#123;</span><br><span class="line">        map.put(nums[i], i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; nums.length; i++) &#123;</span><br><span class="line">        <span class="keyword">int</span> complement = target - nums[i];</span><br><span class="line">        <span class="keyword">if</span> (map.containsKey(complement) &amp;&amp; map.get(complement) != i) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[] &#123; i, map.get(complement) &#125;;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">"No two sum solution"</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h5 id="Complexity-Analysis-1"><a href="#Complexity-Analysis-1" class="headerlink" title="Complexity Analysis"></a>Complexity Analysis</h5><ul>
<li>时间复杂度：$O(n)$，我们把包含有 n 个元素的列表遍历两次。由于哈希表将查找时间缩短到 $O(1)$ ，所以时间复杂度为 $O(n)$。</li>
<li>空间复杂度：$O(n)$，所需的额外空间取决于哈希表中存储的元素数量，该表中存储了 n 个元素。</li>
</ul>
<h4 id="LeetCode-Solution-3-One-pass-Hash-Table"><a href="#LeetCode-Solution-3-One-pass-Hash-Table" class="headerlink" title="LeetCode Solution 3: One-pass Hash Table"></a>LeetCode Solution 3: One-pass Hash Table</h4><p>It turns out we can do it in one-pass. While we iterate and inserting elements into the table, we also look back to check if current element’s complement already exists in the table. If it exists, we have found a solution and return immediately.</p>
<p>事实证明，我们可以一次完成。在进行迭代并将元素插入到表中的同时，我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回。</p>
<h5 id="Code-3"><a href="#Code-3" class="headerlink" title="Code"></a>Code</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[] twoSum(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target) &#123;</span><br><span class="line">    Map&lt;Integer, Integer&gt; map = <span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; nums.length; i++) &#123;</span><br><span class="line">        <span class="keyword">int</span> complement = target - nums[i];</span><br><span class="line">        <span class="keyword">if</span> (map.containsKey(complement)) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[] &#123; map.get(complement), i &#125;;</span><br><span class="line">        &#125;</span><br><span class="line">        map.put(nums[i], i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">"No two sum solution"</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h5 id="Complexity-Analysis-2"><a href="#Complexity-Analysis-2" class="headerlink" title="Complexity Analysis"></a>Complexity Analysis</h5><ul>
<li>时间复杂度：$O(n)$，我们只遍历了包含有 n 个元素的列表一次。在表中进行的每次查找只花费 $O(1)$ 的时间。</li>
<li>空间复杂度：$O(n)$，所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n 个元素。</li>
</ul>
<h2 id="Summary"><a href="#Summary" class="headerlink" title="Summary"></a>Summary</h2><p>因为 LeetCode 提供的 Solution 是依次的基于不同情况下的实现和优化，是逐步递进的，所以我把这三个 Solution 也一起贴过来了。</p>
<p>解决这个问题运用到了 数组（Array） 和 哈希表（Hash Table）两种数据结构。在实际开发中，需要基于不同的情况来使用，比如数据量级小或快速开发，那当然就使用暴力法，怎么简单怎么来。但当涉及到性能时，就要综合考虑选择了。</p>
<h2 id="References"><a href="#References" class="headerlink" title="References"></a>References</h2><ul>
<li><a href="https://leetcode.com/problems/two-sum/" target="_blank" rel="noopener">LeetCode 1. Two Sum</a></li>
<li><a href="https://leetcode-cn.com/problems/two-sum/" target="_blank" rel="noopener">LeetCode CN 1. 两数之和</a></li>
<li><a href="https://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&amp;mid=2247483740&amp;idx=1&amp;sn=1950545589ea9b86ee65fbb6be1f4290&amp;chksm=fa0e6eddcd79e7cb542b7d4dc1304eead516994315fa4f52b575230f0f022c9e0a88ede3714e&amp;scene=21#wechat_redirect" target="_blank" rel="noopener">每天一算：Two Sum</a> 推荐阅读，有 GIF 动画演示。</li>
</ul>

      
    </div>

    

    
    
    

    

    

    
      <div>
        <ul class="post-copyright">
  <li class="post-copyright-author">
    <strong>本文作者： </strong>YamDestiny</li>
  <li class="post-copyright-link">
    <strong>本文链接：</strong>
    <a href="https://yamdestiny.xyz/2019/04/01/leetcode-1-two-sum/" title="[LeetCode] 1. Two Sum">https://yamdestiny.xyz/2019/04/01/leetcode-1-two-sum/</a>
  </li>
  <li class="post-copyright-license">
    <strong>版权声明： </strong>本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" rel="external nofollow" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明出处！</li>
</ul>

      </div>
    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tags/LeetCode/" rel="tag"># LeetCode</a>
          
            <a href="/tags/Algorithms/" rel="tag"># Algorithms</a>
          
        </div>
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2019/03/31/arts-week-0/" rel="next" title="[ARTS] Week 0">
                <i class="fa fa-chevron-left"></i> [ARTS] Week 0
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2019/04/02/leetcode-771-jewels-and-stones/" rel="prev" title="[LeetCode] 771. Jewels and Stones">
                [LeetCode] 771. Jewels and Stones <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          

  
    <div class="comments" id="comments">
      <div id="disqus_thread">
        <noscript>
          Please enable JavaScript to view the
          <a href="https://disqus.com/?ref_noscript">comments powered by Disqus.</a>
        </noscript>
      </div>
    </div>

  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image" src="https://p3.music.126.net/Am30CzvY9NTxy1xiz5k3GQ==/7729566744520405.jpg?param=170y170" alt="YamDestiny">
            
              <p class="site-author-name" itemprop="name">YamDestiny</p>
              <p class="site-description motion-element" itemprop="description">以铜为镜，可以正衣冠；<br>以史为镜，可以知兴替；<br>以人为镜，可以明得失。</p>
          </div>

          
            <nav class="site-state motion-element">
              
                <div class="site-state-item site-state-posts">
                
                  <a href="/archives/">
                
                    <span class="site-state-item-count">49</span>
                    <span class="site-state-item-name">日志</span>
                  </a>
                </div>
              

              
                
                
                <div class="site-state-item site-state-categories">
                  <a href="/categories/index.html">
                    
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                    <span class="site-state-item-count">15</span>
                    <span class="site-state-item-name">分类</span>
                  </a>
                </div>
              

              
                
                
                <div class="site-state-item site-state-tags">
                  <a href="/tags/index.html">
                    
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                    <span class="site-state-item-count">45</span>
                    <span class="site-state-item-name">标签</span>
                  </a>
                </div>
              
            </nav>
          

          

          
            <div class="links-of-author motion-element">
              
                <span class="links-of-author-item">
                  <a href="https://github.com/YamDestiny" target="_blank" title="GitHub"><i class="fa fa-fw fa-github"></i>GitHub</a>
                  
                </span>
              
                <span class="links-of-author-item">
                  <a href="https://steamcommunity.com/id/maple_wqs" target="_blank" title="Steam"><i class="fa fa-fw fa-steam"></i>Steam</a>
                  
                </span>
              
            </div>
          

          
          

          
          

          
            
          
          

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#Question"><span class="nav-number">1.</span> <span class="nav-text">Question</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Example"><span class="nav-number">2.</span> <span class="nav-text">Example</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#Example-1"><span class="nav-number">2.1.</span> <span class="nav-text">Example 1</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#Example-2"><span class="nav-number">2.2.</span> <span class="nav-text">Example 2</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Solution"><span class="nav-number">3.</span> <span class="nav-text">Solution</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#Java"><span class="nav-number">3.1.</span> <span class="nav-text">Java</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#My-Solution-1"><span class="nav-number">3.1.1.</span> <span class="nav-text">My Solution 1</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#解题思路"><span class="nav-number">3.1.1.1.</span> <span class="nav-text">解题思路</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#解题步骤"><span class="nav-number">3.1.1.2.</span> <span class="nav-text">解题步骤</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#Code"><span class="nav-number">3.1.1.3.</span> <span class="nav-text">Code</span></a><ol class="nav-child"><li class="nav-item nav-level-6"><a class="nav-link" href="#初版"><span class="nav-number">3.1.1.3.1.</span> <span class="nav-text">初版</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#优化版"><span class="nav-number">3.1.1.3.2.</span> <span class="nav-text">优化版</span></a></li></ol></li><li class="nav-item nav-level-5"><a class="nav-link" href="#总结"><span class="nav-number">3.1.1.4.</span> <span class="nav-text">总结</span></a></li></ol></li><li class="nav-item nav-level-4"><a class="nav-link" href="#LeetCode-Solution-1-Brute-Force"><span class="nav-number">3.1.2.</span> <span class="nav-text">LeetCode Solution 1: Brute Force</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#Code-1"><span class="nav-number">3.1.2.1.</span> <span class="nav-text">Code</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#Complexity-Analysis"><span class="nav-number">3.1.2.2.</span> <span class="nav-text">Complexity Analysis</span></a></li></ol></li><li class="nav-item nav-level-4"><a class="nav-link" href="#LeetCode-Solution-2-Two-pass-Hash-Table"><span class="nav-number">3.1.3.</span> <span class="nav-text">LeetCode Solution 2: Two-pass Hash Table</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#Code-2"><span class="nav-number">3.1.3.1.</span> <span class="nav-text">Code</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#Complexity-Analysis-1"><span class="nav-number">3.1.3.2.</span> <span class="nav-text">Complexity Analysis</span></a></li></ol></li><li class="nav-item nav-level-4"><a class="nav-link" href="#LeetCode-Solution-3-One-pass-Hash-Table"><span class="nav-number">3.1.4.</span> <span class="nav-text">LeetCode Solution 3: One-pass Hash Table</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#Code-3"><span class="nav-number">3.1.4.1.</span> <span class="nav-text">Code</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#Complexity-Analysis-2"><span class="nav-number">3.1.4.2.</span> <span class="nav-text">Complexity Analysis</span></a></li></ol></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Summary"><span class="nav-number">4.</span> <span class="nav-text">Summary</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#References"><span class="nav-number">5.</span> <span class="nav-text">References</span></a></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; 2017 &mdash; <span itemprop="copyrightYear">2019</span>
  <span class="with-love" id="animate">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">YamDestiny</span>

  

  
</div>




  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动 v3.8.0</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 &mdash; <a class="theme-link" target="_blank" href="https://github.com/theme-next/hexo-theme-next">NexT.Muse</a> v6.3.0</div>




        








        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>


























  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=6.3.0"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=6.3.0"></script>



  
  

  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=6.3.0"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=6.3.0"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=6.3.0"></script>



  

  
    <script id="dsq-count-scr" src="https://yamdestiny.disqus.com/count.js" async></script>
  

  
    <script type="text/javascript">
      var disqus_config = function () {
        this.page.url = 'https://yamdestiny.xyz/2019/04/01/leetcode-1-two-sum/';
        this.page.identifier = '2019/04/01/leetcode-1-two-sum/';
        this.page.title = '[LeetCode] 1. Two Sum';
        };
      function loadComments () {
        var d = document, s = d.createElement('script');
        s.src = 'https://yamdestiny.disqus.com/embed.js';
        s.setAttribute('data-timestamp', '' + +new Date());
        (d.head || d.body).appendChild(s);
      }
      
        $(function () {
          var offsetTop = $('#comments').offset().top - $(window).height();
          if (offsetTop <= 0) {
            // load directly when there's no a scrollbar
            loadComments();
          } else {
            $(window).on('scroll.disqus_scroll', function () {
              var scrollTop = document.documentElement.scrollTop;
              if (scrollTop >= offsetTop) {
                $(window).off('.disqus_scroll');
                loadComments();
              }
            });
          }
        });
      
    </script>
  





	





  












  





  

  
  <script src="https://cdn1.lncld.net/static/js/av-core-mini-0.6.4.js"></script>
  <script>AV.initialize("pc5KAuPRXg1dU4bG8nC957no-gzGzoHsz", "MSoOlaJ0XYd1YN1SbFBCENg2");</script>
  <script>
    function showTime(Counter) {
      var query = new AV.Query(Counter);
      var entries = [];
      var $visitors = $(".leancloud_visitors");

      $visitors.each(function () {
        entries.push( $(this).attr("id").trim() );
      });

      query.containedIn('url', entries);
      query.find()
        .done(function (results) {
          var COUNT_CONTAINER_REF = '.leancloud-visitors-count';

          if (results.length === 0) {
            $visitors.find(COUNT_CONTAINER_REF).text(0);
            return;
          }

          for (var i = 0; i < results.length; i++) {
            var item = results[i];
            var url = item.get('url');
            var time = item.get('time');
            var element = document.getElementById(url);

            $(element).find(COUNT_CONTAINER_REF).text(time);
          }
          for(var i = 0; i < entries.length; i++) {
            var url = entries[i];
            var element = document.getElementById(url);
            var countSpan = $(element).find(COUNT_CONTAINER_REF);
            if( countSpan.text() == '') {
              countSpan.text(0);
            }
          }
        })
        .fail(function (object, error) {
          console.log("Error: " + error.code + " " + error.message);
        });
    }

    function addCount(Counter) {
      var $visitors = $(".leancloud_visitors");
      var url = $visitors.attr('id').trim();
      var title = $visitors.attr('data-flag-title').trim();
      var query = new AV.Query(Counter);

      query.equalTo("url", url);
      query.find({
        success: function(results) {
          if (results.length > 0) {
            var counter = results[0];
            counter.fetchWhenSave(true);
            counter.increment("time");
            
            counter.save(null, {
              success: function(counter) {
                
                  var $element = $(document.getElementById(url));
                  $element.find('.leancloud-visitors-count').text(counter.get('time'));
                
              },
              error: function(counter, error) {
                console.log('Failed to save Visitor num, with error message: ' + error.message);
              }
            });
          } else {
            
              var newcounter = new Counter();
              /* Set ACL */
              var acl = new AV.ACL();
              acl.setPublicReadAccess(true);
              acl.setPublicWriteAccess(true);
              newcounter.setACL(acl);
              /* End Set ACL */
              newcounter.set("title", title);
              newcounter.set("url", url);
              newcounter.set("time", 1);
              newcounter.save(null, {
                success: function(newcounter) {
                  var $element = $(document.getElementById(url));
                  $element.find('.leancloud-visitors-count').text(newcounter.get('time'));
                },
                error: function(newcounter, error) {
                  console.log('Failed to create');
                }
              });
            
          }
        },
        error: function(error) {
          console.log('Error:' + error.code + " " + error.message);
        }
      });
    }

    $(function() {
      var Counter = AV.Object.extend("Counter");
      if ($('.leancloud_visitors').length == 1) {
        addCount(Counter);
      } else if ($('.post-title-link').length > 1) {
        showTime(Counter);
      }
    });
  </script>



  

  

  
  

  
  

  
    
      <script type="text/x-mathjax-config">
    MathJax.Hub.Config({
      tex2jax: {
        inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
        processEscapes: true,
        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
      },
      TeX: {equationNumbers: { autoNumber: "AMS" }}
    });
</script>

<script type="text/x-mathjax-config">
    MathJax.Hub.Queue(function() {
      var all = MathJax.Hub.getAllJax(), i;
        for (i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
        }
    });
</script>
<script type="text/javascript" src="//cdn.jsdelivr.net/npm/mathjax@2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>

    
  


  
  

  

  

  

  

  

</body>
</html>
